from graphviz import Digraph
import random
from copy import deepcopy


class Part:
    def __init__(self, src, edge, dst):
        self.src = src
        self.edge = edge
        self.dst = dst


def move(DFA, src, edge):
    # print("进入move函数.........")
    # print("src:",src,"edge:",edge)
    for i in range(len(DFA)):
        # print("DFA_src:",DFA[i].src[0],"DFA_edge:",DFA[i].edge[0])
        #路径匹配，返回目的结点
        if DFA[i].src[0] == src and DFA[i].edge[0] == edge:
            # print("匹配上了：",DFA[i].src[0],DFA[i].dst[0])
            # print("退出move....")
            return DFA[i].dst[0]
    return ''


def get_source_set(target_set, char, DFA):
    # print("char:",char,"target_set:",target_set)
    global allstatus
    allstatusSet = set(allstatus)
    source_set = set()
    for state in allstatusSet:
        # print("state:",state)
        try:
            #求得目的结点在范围A里面
            if move(DFA, state, char) in target_set:
                # print("进入这个部分....,表示有匹配的点")
                #加入到集合中
                source_set.add(state)
        except KeyError:
            pass
    # print("source_set:",source_set)
    return source_set


def hopcroft_algorithm(DFA):
    # print("进入hopcroft算法部分.........................")
    global sigma
    global endSet
    global allstatus
    #集合形式
    cins = set(sigma)
    #结束状态
    termination_states = set(endSet)
    #全部的状态
    total_states = set(allstatus)
    #不是终止结点的结点
    not_termination_states = total_states - termination_states
    # print("全部状态：",total_states)
    # print("终止结点：",termination_states)
    # print("非终止结点：",not_termination_states)
    P = [termination_states, not_termination_states]
    # print(P)
    W = [termination_states, not_termination_states]
    # print(W)
    # print("===============进入W循环========================")
    while W:
        A = random.choice(W)
        # print("A:",A)
        W.remove(A)
        # print("W:",W)
        # print(",,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,")
        for char in cins:
            #调用函数
            X = get_source_set(A, char, DFA)
            # print("X:",X)
            P_temp = []
            for Y in P:
                S = X & Y
                S1 = Y - X
                if len(S) and len(S1):
                    P_temp.append(S)
                    P_temp.append(S1)

                    if Y in W:
                        W.remove(Y)
                        W.append(S)
                        W.append(S1)
                    else:
                        if len(S) <= len(S1):
                            W.append(S)
                        else:
                            W.append(S1)
                else:
                    P_temp.append(Y)
            P = deepcopy(P_temp)
    return P


def indexMinList(minList, a):
    for i in range(len(minList)):
        if a in minList[i]:
            return i
    return ''


DFA = []
DFA2 = []
#字典
DFADic = {}
#转移条件
sigma = ['a', 'b']
# dot = Digraph(comment='The Test Table')
#画图用的代码
dot = Digraph("DFA")
#数量
num = int(input('input:'))
for i in range(num):
    #起始结点
    x = input()
    #边
    y = input()
    #终止结点
    z = input()
    temp = []
    temp.append(x)
    temp.append(y)
    #temp:[该条转移条件的起始结点，转移条件]
    # print("temp:",temp)
    #将temp放入DFA2中
    DFA2.append(temp)
    DFADic[tuple(temp)] = y
    # print(DFADic)
    temp = Part(x, y, z)
    #DFA里面存放的是全部的转移关系
    DFA.append(temp)
    # if i == 1:
    #     dot.node(name=x, color='blue')
    #     dot.edge(x, z, y)
    # else:
    #     dot.node(name=x, color='black')
    #     dot.edge(x, z, y)
# print("第一个循环结束")
# print(len(DFA))
for i in range(len(DFA)):
    print(DFA[i].src, DFA[i].edge, DFA[i].dst)

endSet = []
endNum = int(input('input end num:'))
for i in range(endNum):
    temp = input()
    endSet.append(temp)
# print("结束状态：",endSet)

startSet = []
allSet = []

for i in range(len(DFA)):
    #起始节点如果不等同于终止结点
    if DFA[i].src[0] not in endSet:
        #将当前结点归为非终止结点里面
        startSet.append(DFA[i].src[0])
    if DFA[i].dst[0] not in endSet:
        #目的结点不是终止结点的也放入非终止结点里面
        startSet.append(DFA[i].src[0])
print("............................")
allstatus = startSet
print(allstatus)
allstatus.extend(endSet)
print(allstatus)
print("...........................")
# dot.render('DFA.gv', view=True)
minList = hopcroft_algorithm(DFA)
minDFA = []
print("=========================================================================================================")
print(minList)

for i in range(len(minList)):
    dstList = [0, 0]  # 用来存储每种状态经过a和b变换后的结果
    for j in range(len(minList[i])):
        listi = list(minList[i])
        if dstList[0] == 0 and move(DFA, listi[j], sigma[0]) != '' and indexMinList(minList, move(DFA, listi[j],
                                                                                                  sigma[0])) != '':
            print(indexMinList(minList, move(DFA, listi[j], sigma[0])))
            dstList[0] = min(minList[indexMinList(minList, move(DFA, listi[j], sigma[0]))])
            # 使用Min函数的原因是为了重新给每种状态命名，选去每个状态中的最小的即可

        if dstList[1] == 0 and move(DFA, listi[j], sigma[1]) != '' and indexMinList(minList, move(DFA, listi[j],
                                                                                                  sigma[1])) != '':
            dstList[1] = min(minList[indexMinList(minList, move(DFA, listi[j], sigma[1]))])
    if dstList[0] != 0:
        temp = Part(min(minList[i]), 'a', dstList[0])
        minDFA.append(temp)
    if dstList[1] != 0:
        temp2 = Part(min(minList[i]), 'b', dstList[1])
        minDFA.append(temp2)

# dot2 = Digraph('测试图片')
#
# for i in range(len(minDFA)):
#     print(minDFA[i].src, minDFA[i].edge, minDFA[i].dst)
#     if i == 1:
#         dot2.node(name=minDFA[i].src, color='red')
#         dot2.edge(minDFA[i].src, minDFA[i].dst, minDFA[i].edge)
#     else:
#         dot2.node(name=minDFA[i].src, color='black')
#         dot2.edge(minDFA[i].src, minDFA[i].dst, minDFA[i].edge)

# dot2.render('minDFA.gv', view=True)